package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC2002 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        Map<String, Integer> memo = new HashMap<>();

        public int maxProduct(String s) {
            return dfs(s, 0, new StringBuilder(), new StringBuilder());
        }

        public int dfs(String s, int i, StringBuilder aSet, StringBuilder bSet) {
            if (i >= s.length()) return getPalindromeLength(aSet) * getPalindromeLength(bSet);
            String key = aSet.toString() + "_" + bSet.toString() + "_" + i;
            if (memo.containsKey(key)) return memo.get(key);

            // 当前 i位置有3种选择：
            // 1 不选择任意 集合
            int notChoose = dfs(s, i + 1, aSet, bSet);

            int chooseASet = 0;
            aSet.append(s.charAt(i));
            chooseASet = dfs(s, i + 1, aSet, bSet);
            aSet.deleteCharAt(aSet.length() - 1);

            int chooseBSet = 0;
            bSet.append(s.charAt(i));
            chooseBSet = dfs(s, i + 1, aSet, bSet);
            bSet.deleteCharAt(bSet.length() - 1);

            int ans = Math.max(notChoose, Math.max(chooseASet, chooseBSet));
            memo.put(key, ans);
            return ans;
        }

        public int getPalindromeLength(StringBuilder aSet) {
            if (aSet.length() <= 1) return aSet.length();
            boolean isPalindrome = true;

            int endSearchPos = aSet.length() % 2 == 0 ? (aSet.length() - 1) / 2 : (aSet.length() + 1) / 2 - 1;
            for (int i = 0; i <= endSearchPos; i++) {
                if (aSet.charAt(i) != aSet.charAt(aSet.length() - i - 1)) {
                    isPalindrome = false;
                    break;
                }
            }

            return isPalindrome ? aSet.length() : 0;
        }
    }

    public void run() {
        System.out.println(new Solution().maxProduct("aba"));
        System.out.println(new Solution().maxProduct("leetcodecom"));
        System.out.println(new Solution().maxProduct("bb"));
        System.out.println(new Solution().maxProduct("accbcaxxcxx"));
    }

    public static void main(String[] args) throws Exception {
        LC2002 an = new LC2002();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
